#
# @lc app=leetcode.cn id=1143 lang=python3
#
# [1143] 最长公共子序列
#

# @lc code=start
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp[i][j]表示[0,i-1]的text1和[0,j-1]的text2,它们的最长公共子序列
        # 这样定义的好处,初始化简单,dp[i][0]和dp[0][j]简单初始化为0,应为此处是空字串.
        n1, n2 = len(text1)+1, len(text2)+1
        # 行n1,列n2
        dp = [[0]*n2 for _ in range(n1)]
        # 循环范围 [1~n+1) -> [0->n)
        for i in range(1, n1):
            for j in range(1, n2):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            #     print(f'dp[{i}][{j}]={dp[i][j]}', end=' ')
            #     print(text1[0: i], text2[0: j], end=' ')
            # print()
        return dp[n1-1][n2-1]
# @lc code=end

